/* File - sudoku_solver.c   */

#include <stdio.h>
#include <string.h>
#include <math.h>

#define MAX_NUM 100
static unsigned column_stats[MAX_NUM] = {0};
static unsigned row_stats[MAX_NUM] = {0};
static unsigned region_stats[MAX_NUM] = {0};
static short unsigned column_bit_count[MAX_NUM] = {0};
static short unsigned row_bit_count[MAX_NUM] = {0};
static short unsigned region_bit_count[MAX_NUM] = {0};
static short size_of_region = 0;
static short size_of_sudoku = 0;

/* Function Declarations . */

void display(unsigned int sudoku[][MAX_NUM], int n);
void init(unsigned sudoku[][MAX_NUM], char *filename );
void set_bit(int *stat, int filled_num);
void count_bits(unsigned elem[], int n, short unsigned elem_bit_count[]);
unsigned fill_region(unsigned sudoku[][MAX_NUM], int region_num, int n);
unsigned fill_region_method_2(unsigned sudoku[][MAX_NUM], int region_num, int n);
unsigned apply_rule_2(int row_num, int col_num, int num_to_be_fixed);

int main(int argc, char *argv[])
{
    char rerun = 'y';
    int i,j,m;
    unsigned sudoku[MAX_NUM][MAX_NUM]= {0};

    if(argc > 1)
    {
        init(sudoku, argv[1]);
    }else
    {
        printf("\nerror : No file to read input!!!\n");
        return -1;
    }
    display(sudoku, size_of_region);
    j =0;
    unsigned sudoku_complete;
    do
    {
        for(i =0; i<size_of_sudoku; i++)
        {
            if(region_bit_count[i] != size_of_sudoku)
	    {
	        fill_region(sudoku, i, size_of_region);
	        fill_region_method_2(sudoku, i, size_of_region);
	    }else if(region_bit_count[i] == size_of_sudoku)
	    {
	      sudoku_complete = region_stats[i];
	      for(m=0; m< size_of_sudoku; m++)
	      {
	          sudoku_complete &=region_stats[m];
	      }
	      if(sudoku_complete == (pow(2,size_of_sudoku) - 1))
	      break;
	    }
	}
	if(sudoku_complete == (pow(2,size_of_sudoku) - 1))
	rerun = 'n';

    }while(rerun == 'y');

   return 0;
}

void display(unsigned int sudoku[][MAX_NUM], int n)
{
    int i =0, j=0, offset =0;
    for(i=0; i<(n*n); i++)
    {
        if((i%n) == 0)
	{
            printf("\n\t+---+---+---+---+---+---+---+---+---+\n\t| ");
	    offset = i;
	}
        else
        printf("\n\t------------+-----------+-----------+\n\t| ");
        for(j=0;j<(n*n);j++)
        {
            if((sudoku[i][j]))
            {
                printf("%d | ",(sudoku[i][j]));
		set_bit(&row_stats[i], sudoku[i][j]);
		set_bit(&column_stats[j], sudoku[i][j]);
		set_bit(&region_stats[(offset)+(j/n)], sudoku[i][j]);
            }
            else
                printf("  | ");
        }
    }
    printf("\n\t+---+---+---+---+---+---+---+---+---+\n\n ");

   count_bits(row_stats, n, row_bit_count); 
   count_bits(column_stats, n, column_bit_count); 
   count_bits(region_stats, n, region_bit_count); 
}

void set_bit(int *stat, int filled_num)
{
   int num;

//   num = pow(2, filled_num-1);

   num = (1 << (filled_num-1));

    if(!((*stat)&(num)))
   *stat += num;
}



unsigned NumberOfSetBits(unsigned i)
{
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return ((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

void count_bits(unsigned elem[], int n, short unsigned elem_bit_count[])
{ 
   int i=0, j=0;

   for(;i<(n*n);i++)
   {
       elem_bit_count[i] = NumberOfSetBits(elem[i]);
   }
}


void init(unsigned sudoku[][MAX_NUM], char *filename)
{
#if 0
sudoku[0][0] = 7;
sudoku[0][1] = 8;
sudoku[0][4] = 3;
sudoku[0][5] = 5;

sudoku[1][3] = 7;
sudoku[1][4] = 2;
sudoku[1][5] = 1;
sudoku[1][8] = 3;

sudoku[2][0] = 3;
sudoku[2][2] = 4;
sudoku[2][6] = 5;

sudoku[3][1] = 7;
sudoku[3][2] = 9;
sudoku[3][3] = 1;
sudoku[3][6] = 8;
sudoku[3][7] = 3;

sudoku[4][0] = 1;
sudoku[4][3] = 3;
sudoku[4][5] = 8;
sudoku[4][8] = 2;

sudoku[5][1] = 3;
sudoku[5][2] = 8;
sudoku[5][5] = 4;
sudoku[5][6] = 7;
sudoku[5][7] = 1;

sudoku[6][2] = 3;
sudoku[6][6] = 2;
sudoku[6][8] = 9;


sudoku[7][0] = 8;
sudoku[7][3] = 2;
sudoku[7][4] = 4;
sudoku[7][5] = 3;

sudoku[8][3] = 9;
sudoku[8][4] = 5;
sudoku[8][7] = 4;
sudoku[8][8] = 8;

////////////////////////////
sudoku[0][0] = 5;
sudoku[0][4] = 8;
sudoku[0][5] = 9;
sudoku[0][7] = 6;

sudoku[1][3] = 2;
sudoku[1][7] = 5;

sudoku[2][2] = 8;
sudoku[2][3] = 7;
sudoku[2][4] = 5;
sudoku[2][5] = 3;
sudoku[2][7] = 9;

sudoku[3][0] = 7;
sudoku[3][2] = 9;
sudoku[3][8] = 5;

sudoku[4][0] = 2;
sudoku[4][8] = 6;

sudoku[5][0] = 8;
sudoku[5][6] = 9;
sudoku[5][8] = 1;

sudoku[6][1] = 6;
sudoku[6][3] = 8;
sudoku[6][4] = 1;
sudoku[6][5] = 2;
sudoku[6][6] = 5;

sudoku[7][1] = 8;
sudoku[7][5] = 7;

sudoku[8][1] = 2;
sudoku[8][3] = 5;
sudoku[8][4] = 6;
sudoku[8][8] = 8;
#endif

int i, j, n;
FILE *fp;

fp = fopen(filename, "r");

fscanf(fp, "%d ", &n);
size_of_sudoku = n;
size_of_region =  sqrt(n);

for(i=0; i<n; i++)
for(j=0; j<n; j++)
fscanf(fp, "%d ", &sudoku[i][j]);
}

unsigned get_starting_row(unsigned region, int n)
{
    return((region/n)*n);
}

unsigned get_starting_column(unsigned region, int n)
{
    return((region%n)*n);
}

unsigned apply_rule_1(int reg_num, int row_num, int col_num, int n)
{
    unsigned result;
    unsigned num_of_zeroes =0;
    unsigned number;
    int i;

    result = region_stats[reg_num] | column_stats[col_num] |row_stats[row_num];
    for(i=0;i<(n*n);i++)
    {
        if(0 == (result &(1 << i)))
	{
	    num_of_zeroes++;
	    number = i+1;
	}
    }
    if(num_of_zeroes == 1)
    {
       return number;
    }else
    return 0;
}

unsigned apply_rule_2(int row_num, int col_num, int num_to_be_fixed)
{
    int row_result = 1;
    int col_result = 1;

    row_result =  row_stats[row_num] & (1 << (num_to_be_fixed));
    col_result =  column_stats[col_num] & (1 << (num_to_be_fixed));

    if(row_result || col_result)
        return 0;
    else
        return 1;
}

unsigned fill_region(unsigned sudoku[][MAX_NUM], int region_num, int n)
{
    	
    int s_row;
    int s_col;
    int i = 0;
    int j= 0 ;
    int fixed_num = 0;

    s_row = get_starting_row(region_num, n);
    s_col = get_starting_column(region_num, n);

    for(i=s_row;i<(s_row+n);i++ )
    {
    
    	for(j = s_col;j<(s_col+n);j++)
	{
		if(!sudoku[i][j])
	        {
			fixed_num = apply_rule_1(region_num, i, j, n);
			if(fixed_num  > 0)
			{
			      sudoku[i][j] = fixed_num;
			      display(sudoku, n);
			}
		} 
	}
    }
}


unsigned fill_region_method_2(unsigned sudoku[][MAX_NUM], int region_num, int n)
{
    	
    int s_row;
    int s_col;
    int i = 0;
    int j= 0 ;
    int k= 0 ;
    int row_pos, col_pos ;
    int fixed_num = 0;

    s_row = get_starting_row(region_num, n);
    s_col = get_starting_column(region_num, n);

    for(k=0;k<(n*n); k++)
    {
        fixed_num =0; 
        if(0 == (region_stats[region_num] &(1 << k)))
	{
            for(i=s_row;i<(s_row+n);i++ )
            {
        
        	    for(j = s_col;j<(s_col+n);j++)
        	    {
        		if(!sudoku[i][j])
        	        {
				if (apply_rule_2(i, j, k))
				{
				    fixed_num ++;
				    row_pos = i;
				    col_pos = j;
				}
        		} 
    	            }
            }
            if(fixed_num  == 1)
            {
                sudoku[row_pos][col_pos] = k+1;
                display(sudoku, n);
            }
	}
    }
}

